import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution1To100 {
    /**
     * 第一题
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums,int target){
        for(int i = 0;i<nums.length;i++){
            for(int j = 0;j<nums.length;j++){
                if(j==i)
                    continue;
                if(nums[i] + nums[j] == target)
                    return new int[]{i,j};
            }
        }
        return null;
    }

    /**
     * 第二题
     * @param l1
     * @param l2
     * @return
     */
    public TitleTwoNode addTwoNumber(TitleTwoNode l1, TitleTwoNode l2){
        TitleTwoNode x = new TitleTwoNode(0);
        TitleTwoNode p = l1,q = l2,y = x;

        int carry = 0;

        while (p != null||q != null){
            int i = (p!=null) ? p.val : 0;
            int j = (q!=null) ? q.val : 0;

            int sum = carry + i + j;
            carry = sum / 10;
            y.next = new TitleTwoNode(sum%10);
            y = y.next;
            if(p!=null)p = p.next;
            if(q!=null)q = q.next;
        }
        if(carry > 0)
            y.next = new TitleTwoNode(carry);
        return x.next;
    }
    class TitleTwoNode {
        int val;
        TitleTwoNode next;
        TitleTwoNode(int x){val = x;}
    }

    /**
     * 第三题
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s){
        if(s.equals(""))
            return 0;
        int left = 0,right = 1,count = 1;
        boolean isRepeate = false;
        char[] x = s.toCharArray();
        while (right < x.length){
            for(int i = left;i<right;i++){
                if(x[i] == x[right]){
                    isRepeate = true;
                    left = i+1;
                    break;
                }
            }
            if(isRepeate){
                if(left == right)
                    right++;
            }else {
                count = (right-left+1)>count?(right-left+1):count;
                right++;
            }
            isRepeate = false;
        }
        return count;
    }

    /**
     * 第四题
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int totalLength = nums1.length + nums2.length;

        if(totalLength % 2 == 1){
            double median = getKthElement(nums1,nums2,totalLength/2 + 1);
            return median;
        }else {
            int midIndex1 = totalLength/2,midIndex2 = totalLength/2 + 1;
            double median = (getKthElement(nums1,nums2,midIndex1) + getKthElement(nums1,nums2,midIndex2)) / 2.0;
            return median;
        }
    }
    public int getKthElement(int[] nums1,int[] nums2,int k){
        int length1 = nums1.length,length2 = nums2.length;
        int index1 = 0,index2 = 0;

        while (true){
            if(index1 == length1)
                return nums2[index2 + k -1];
            if(index2 == length2)
                return nums1[index1 + k -1];
            if(k == 1)
                return Math.min(nums1[index1],nums2[index2]);

            int half = k/2;
            int newIndex1 = Math.min(index1 + half,length1) - 1;
            int newIndex2 = Math.min(index2 + half,length2) -1;
            if(nums1[newIndex1] < nums2[newIndex2]){
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            }else {
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }

    /**
     * 第五题
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len <= 1){
            return s;
        }
        int maxLen = 1;
        String res = s.substring(0,1);
        for(int i = 0;i<len - 1;i++){
            String Str1 = centerSpread(s,i,i);
            String Str2 = centerSpread(s,i,i+1);
            String MaxLenStr = Str1.length() > Str2.length() ? Str1:Str2;
            if(MaxLenStr.length() > maxLen){
                maxLen = MaxLenStr.length();
                res = MaxLenStr;
            }
        }
        return res;

    }
    public String centerSpread(String s,int left,int right){
        int len = s.length();
        int i = left;
        int j = right;
        while (i >= 0&&j < len){
            if(s.charAt(i) == s.charAt(j)){
                i--;
                j++;
            }else {
                break;
            }
        }
        return s.substring(i+1,j);
    }

    /**
     * 第六题
     * @param s
     * @param numRows
     * @return
     */
    public String convert(String s, int numRows) {
        if(numRows < 2) return s;
        List<StringBuilder> x = new ArrayList<>();
        int flag = 1;
        int y = 0;
        for (int i=0;i<numRows;i++)x.add(new StringBuilder());

        for (char c:s.toCharArray()) {
            x.get(y).append(c);
            y += flag;
            if(y == 0 || y == x.size() - 1){
                flag = -flag;
            }
        }
        StringBuilder res = new StringBuilder();
        for (StringBuilder sb:x
             ) {
            res.append(sb);
        }
        return res.toString();
    }

    /**
     * 第七题
     * @param x
     * @return
     */
    public int reverse(int x) {
        int res = 0;
        int i = 0;
        while(x != 0){
            i = x%10;

            if(res > 214748364 || (res == 214748364 && i > 7)){
                return 0;
            }
            if(res < -214748364 || (res == -214748364 && i < -7)){
                return 0;
            }

            res = res*10 + i;
            x /= 10;
        }

        return res;
    }

    /**
     * 第八题
     * @param str
     * @return
     */
    public int myAtoi(String str) {
        int res = 0;
        int index = 0;

        int len = str.length();
        char[] chars = str.toCharArray();
        while (index < str.length()&&chars[index] == ' '){
                index++;
        }
        if(index == len) return 0;

        int sign = 1;
        if(chars[index] == '+'){
            index++;
        }else if(chars[index] == '-'){
            index++;
            sign = -1;
        }

        while (index < len){
            char currChar = chars[index];

            if(currChar > '9' || currChar < '0'){
                break;
            }

            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (currChar - '0') > Integer.MAX_VALUE % 10)) {
                return Integer.MAX_VALUE;
            }
            if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (currChar - '0') > -(Integer.MIN_VALUE % 10))) {
                return Integer.MIN_VALUE;
            }

            res = res*10 + sign*(currChar-'0');
            index++;
        }
        return res;

    }

    /**
     * 第九题
     * @param x
     * @return
     */
    public boolean isPalindrome(int x) {
        if(x<0||(x%10==0&&x!=0)) return false;
        int reverteNumber = 0;
        while (x>reverteNumber){
            reverteNumber = reverteNumber * 10 + x%10;
            x/=10;
        }
        return x==reverteNumber||x==reverteNumber/10;
    }

    /**
     * 第十题
     * @param s
     * @param p
     * @return
     */
    public boolean isMatch(String s,String p){
        char[] str = s.toCharArray(), ptr = p.toCharArray();
        boolean[][] dp = new boolean[str.length + 1][ptr.length + 1];
        dp[0][0] = true;
        for (int i = 0; i <= str.length; i++) {
            for (int j = 1; j <= ptr.length; j++) {
                if(ptr[j - 1] != '*') {
                    if(i > 0 && (str[i - 1] == ptr[j - 1] || ptr[j - 1] == '.')) dp[i][j] = dp[i - 1][j - 1];
                }else { //ptr[j - 1] == '*'
                    if(j > 1) dp[i][j] |= dp[i][j - 2];   //无匹配
                    if(i > 0 && j > 1 && (str[i - 1] == ptr[j - 2] || ptr[j - 2] == '.'))dp[i][j] |= dp[i - 1][j];    //有匹配
                }
            }
        }
        return dp[str.length][ptr.length];
    }

    /**
     * 第十一题
     * @param height
     * @return
     */
    public int maxArea(int[] height){
        int maxArea = 0;
        int left = 0;
        int right = height.length-1;
        while (left != right){
            maxArea = Math.max(maxArea,(Math.min(height[left],height[right])*(right-left)));
            if(height[left]>height[right])
                right--;
            else
                left++;
        }
        return maxArea;
    }

    /**
     *第十二题
     * @param num
     * @return
     */
    public String intToRoman(int num) {
        String[] loma = {"I","V","X","L","C","D","M"};
        int step = 0;
        StringBuilder res = new StringBuilder();
        for(int x = num;x != 0;x/=10,step +=2){
            int y = x%10;
            if(y == 4){
                res.insert(0,loma[step] + loma[step+1]);
                continue;
            }
            if(y == 9){
                res.insert(0,loma[step] + loma[step+2]);
                continue;
            }
            for(int i = 0;i<y%5;i++){
                res.insert(0,loma[step]);
            }
            if(y/5 != 0)res.insert(0,loma[step+1]);
        }
        return res.toString();
    }

    public int romanToInt(String s){
        Map<String,Integer> map = new HashMap<>();
        map.put("I", 1);
        map.put("IV", 4);
        map.put("V", 5);
        map.put("IX", 9);
        map.put("X", 10);
        map.put("XL", 40);
        map.put("L", 50);
        map.put("XC", 90);
        map.put("C", 100);
        map.put("CD", 400);
        map.put("D", 500);
        map.put("CM", 900);
        map.put("M", 1000);

        int res = 0;
        for(int i = 0;i<s.length();){
            if(i+1<s.length()&&map.containsKey(s.substring(i,i+2))){
                res += map.get(s.substring(i,i+2));
                i+=2;
            }else {
                res += map.get(s.substring(i,i+1));
                i++;
            }
        }
        return  res;
    }
}
